package com.icecoding.linked_lists;

/**
 * 142.环形链表 II
 */
public class detectCycle {
    public ListNode detectCycleSolution(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            //快慢指针相遇时,快指针比满指针多走k, k = 环的路径的整数倍
            //设相遇点距离环的起始点距离m
            //则慢指针走到环起始点距离为 k - m
            //  快指针走到环起始点距离为 k - m
            if(fast == slow){
                break;
            }
        }
        if(head == null || head.next == null){
            return null;
        }
        //满指针回到链表头部
        slow = head;
        while(slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        detectCycle detectCycle = new detectCycle();
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head;
        ListNode result = detectCycle.detectCycleSolution(head);
        System.out.println(result.val);
    }
}
